P3232 [HNOI2013]游走

这道题边的数量最高是10000多，而点只有500，这提醒我们，我们不能直接对边求期望，而是点。

设$Expection[u]$表示点$u$的期望走过次数，$Degree[u]$表示点$u$的度数。

那么，

$Expection[u]=\sum_{v \in u}\frac{Expection[v]}{Degree[v]}$

但是，你会发现，$Expection[v]$要依靠$Expection[u]$，不能直接计算。

再次观察后，既然每一项都有其他项，类似方程形式，那我们可以用高斯消元解决，计算出每一点的$Expection$。

然后，我们先不考虑边权，根据点算出边的期望，当点$u,v$之间存在一条边时，$(u,v)$这条边显然只与点$u,v$有关，且该边的期望为：

$Expection(u,v)=\frac{Expection[u]}{Degree[u]}+\frac{Expection[v]}{Degre[v]}$

之后，利用贪心的思想，期望经过值越大，我们就分配越小的权值，统计一下答案就好了。

注意：边数可达点数平方/2，跟边有关的数组开 $\text{MAXN}$ 的平方。

// luogu-judger-enable-o2
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-10

const int MAXN = 500;
int n , m , u , v , Degree[ MAXN + 5 ] , S[ MAXN * MAXN ] , T[ MAXN * MAXN ];
double a[ MAXN + 5 ][ MAXN + 5 ] , Expection[ MAXN * MAXN + 5 ]; //a数组为点i到点n，点i的期望走过次数
vector< int > Graph[ MAXN + 5 ];

void Gauss( ) {
    int Row , Column;
    for( int i = 1 ; i < n ; i ++ ) {
        Column = i;
        for( int j = i ; j <= n ; j ++ )
            if( fabs( a[ j ][ i ] ) > fabs( a[ Column ][ i ] ) )
                Column = j;
        swap( a[ i ] , a[ Column ] );
        for( int j = n ; j >= i ; j -- ) 
        	a[ i ][ j ] /= a[ i ][ i ];
        for( int j = 1 ; j < n ; j ++ )
            if( i != j )
				for( int k = n ; k >= i ; k -- )
                	a[ j ][ k ] -= a[ j ][ i ] * a[ i ][ k ];
    }
}

int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&u,&v);
        Degree[ u ] ++ , Degree[ v ] ++;
        Graph[ u ].push_back( v );
        Graph[ v ].push_back( u );
        S[ i ] = u , T[ i ] = v;
    }
    a[ 1 ][ n ] = 1;
    for( int i = 1 ; i < n ; i ++ )  {
        a[ i ][ i ] = 1;
        for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
            int v = Graph[ i ][ j ];
            if( v != n ) a[ i ][ v ] = -1.0 / Degree[ v ];
        }
    }
    Gauss( );

    for( int i = 1 ; i <= m ; i ++ ) {
        if( S[ i ] != n )
            Expection[ i ] += a[ S[ i ] ][ n ] * ( 1.0 / Degree[ S[ i ] ] );
        if( T[ i ] != n )
            Expection[ i ] += a[ T[ i ] ][ n ] * ( 1.0 / Degree[ T[ i ] ] );
    }
    sort( Expection + 1 , Expection + m + 1 );

    double Ans = 0;
    for( int i = 1 ; i <= m ; i ++ )
        Ans += Expection[ i ] * 1.0 * ( m - i + 1 );
    printf("%.3lf",Ans);
    return 0;
}